package LeetCodeHot100TopInterview;

public class Q189_RotateArr {

    //旋转数组
    //给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数
    //要求原地算法


    //额外空间 : newArr[(i + k) % n] = nums[i]
    //待定
    public void rotate(int[] nums, int k) {

        //向右移动 K 位后
        // 后K % Len 位元素会到数组前
        //先整体反转 让后K % Len 位元素到前面来
        reverse(nums, 0, nums.length - 1);
        //然后分别反转 ==> 恢复过程
        reverse(nums, 0, (k % nums.length) - 1);
        reverse(nums, (k % nums.length), nums.length - 1);
    }

    //反转
    public void reverse(int[] nums, int start, int end){
        int left = start;
        int right = end;
        while (left < right){
            int tmp = nums[left];
            nums[left++] = nums[right];
            nums[right--] = tmp;
        }
    }
}
